﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;


namespace BusinessTier
{
    class Dijkstra
    {

        private BasicGraphImpl graph;
       
        

        public Dijkstra(BasicGraphImpl graph)
        {
            this.graph = graph;
            
            
        }

        public List<Vertex> getCheapestRoute(Vertex startingVertex, String destinationName)
        {

            List<Vertex> verticesWithCosts;

            // Initilize the costs to every vertex, 
            // the cost  to the starting vertex is 0.
            verticesWithCosts = BuildInitialCostsList(startingVertex);

            //Calculate the costs to every vertex in the list.
            CalculateCosts(verticesWithCosts); 


            return CheapestRoute(startingVertex, destinationName, verticesWithCosts);


 

          
        }

  




        private List<Vertex> BuildInitialCostsList(Vertex startingVertex)
        {


            IEnumerator i = graph.Vertices();

            //Unmark all the vertices and initilize the costs 
            // for getting to them.
            this.graph.UnMark();  

            List<Vertex> verticesWithCosts = new List<Vertex>();

            while (i.MoveNext())
            {
                Vertex v = (Vertex)i.Current;

                //The chepest way to get to this vertex from the starting one (it is null for now).
                v.PreviousVertex = null; 


                if (v.Name.Equals(startingVertex.Name))
                {
                    // Initilize the cost to the starting vertex.
                    v.PriceToGetHere = 0.0;  
                }
                else
                {
                    // Initilzie the cost to all the other vertices.
                    v.PriceToGetHere = Double.MaxValue; 
                }

                verticesWithCosts.Add(v);

            }

            return verticesWithCosts;

        }

        private void CalculateCosts(List<Vertex> costs)
        {


            while (hasMoreUnivisited(costs))
            {
                //Find to which vertex we can get on the lowest possible cost.
                Vertex nextVertex = NextUnvisitedLowestCostIndex(costs);

                //Mark the vertex as visited.
                nextVertex.Mark = true;


                //Iterate trough all the adjacencies of the vertex.
                foreach (Vertex adjacencyVertex in graph.GetAdjacencies(nextVertex))   
                {

                    //The current cost to get to the adjacency.
                    double currentCost = adjacencyVertex.PriceToGetHere;

                    //Compare the costs.
                    if (currentCost > nextVertex.getLegWithLowestPrice(adjacencyVertex).Price + nextVertex.PriceToGetHere) 
                    {
                        //Assign the new costs.
                        adjacencyVertex.PriceToGetHere = nextVertex.getLegWithLowestPrice(adjacencyVertex).Price + nextVertex.PriceToGetHere;

                        //Assign the nextVertex as the cheapest way to get to the adjacencyVertex. 
                        adjacencyVertex.PreviousVertex = nextVertex;

                    }

                }


            }




        }


        // Build up the cheapest route from the startingVertex to the destinationVertex according the costs.

        private List<Vertex> CheapestRoute(Vertex startingVertex, String destinationName, List<Vertex> verticesWithCosts)
        {
            List<Vertex> cheapestRoute = new List<Vertex>();

            bool routeIsReady = false;
            String destination = destinationName;

            while (!routeIsReady)
            {


                foreach (Vertex currentVertex in verticesWithCosts)
                {
                  

                    if (currentVertex.Name.Equals(destination))
                    {
                        //Add the vertex to the route.
                        cheapestRoute.Add(currentVertex); 

                        if (destination.Equals(startingVertex.Name))
                        {
                            routeIsReady = true;
                            
                        }

                        else
                        {
                            Vertex previousVertex=currentVertex.PreviousVertex;
                            if (previousVertex == null)
                            {
                                //Route was not found.
                                cheapestRoute = null;  
                                routeIsReady = true;
                              
                            }

                            else
                            {

                                //Add it as next target.
                                destination = previousVertex.Name; 
                            }
                        }

                        //Stop the foreach loop. 
                        break;  
                    }

                }
            }



            return cheapestRoute; 
        
        }

        private bool hasMoreUnivisited(List<Vertex> costs)
        {

            if (NextUnvisitedLowestCostIndex(costs) == null)
            {
                //No more elements remaning
                return false;
            }

            else
                return true;


          //foreach(DijkstraVertex costInfo in costs)
          //{
          //    Vertex v = costInfo.CurrentVertex;
          //    if (!v.Mark)
          //    {
          //        return true;
          //    }
          //}

          //return false;
        }


        //Get the index of the list with next unvisited vertex with lowest cost
        private Vertex NextUnvisitedLowestCostIndex(List<Vertex> costs)
        {
            //List of of all the unvisited vertecies.
            List<Vertex> unvisitedVertecies=new List<Vertex>();


            foreach (Vertex v in costs)
            {
                //Check if the vertex is not already visited.
               if (v.Mark) 
                   continue;

               //Add the unvisited vertex to the list.
               unvisitedVertecies.Add(v); ; 

             
            }


            //Find the one with the lowest cost.
            Vertex nextVertex = null;
            double lowestCost = Double.MaxValue;

            foreach (Vertex unvisitedVertex in unvisitedVertecies)
            {


                double cost = unvisitedVertex.PriceToGetHere;
              
             
                if (cost < lowestCost)
                {
                    lowestCost = cost;
                    nextVertex = unvisitedVertex;
                }
            
            }

            return nextVertex;
        
        }
    }
}
